#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int longestPalindromicSubsequence(string s, int k)
    {
        int n = s.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k + 1, 0)));
        // for(int ik = 0 ; ik <= k; ++ik){
        for (int i = 0; i < n; ++i)
        {
            dp[i][i][0] = 1;
            dp[i][i][1] = 1;
        }
        // }
        int ans = 1;
        for (int ik = 0; ik <= k; ik++)
        {
            for (int i = n - 1; i >= 0; --i)
            {
                for (int j = i + 1; j < n; ++j)
                {
                    int del = abs(s[i] - s[j]);
                    del = min(del, 26-del);
                    dp[i][j][ik] = max(0, dp[i][j][ik]);
                    // not choose i
                    dp[i][j][ik] = max(dp[i][j][ik], dp[i+1][j][ik]);
                    // not choose j
                    dp[i][j][ik] = max(dp[i][j][ik], dp[i][j-1][ik]);
                    // choose both
                    if(ik >= del)
                        dp[i][j][ik] = max(dp[i][j][ik], dp[i+1][j-1][ik-del] + 2);
                    ans = max(ans, dp[i][j][ik]);
                }
            }
        }
        return ans;
    }
};
